﻿namespace AdvancedTraining.Lesson36;

/// <summary>
/// 来自美团的高效查询问题
/// </summary>
/// <remarks>
/// 给定一个数组arr，长度为N，做出一个结构，可以高效的做如下的查询：
/// 1) int QuerySum(L,R) : 查询arr[L...R]上的累加和
/// 2) int QueryAim(L,R) : 查询arr[L...R]上的目标值，目标值定义如下：
///        假设arr[L...R]上的值为[a,b,c,d]，a+b+c+d = s
///        目标值为 : (s-a)^2 + (s-b)^2 + (s-c)^2 + (s-d)^2
/// 3) int QueryMax(L,R) : 查询arr[L...R]上的最大值
///
/// 要求：
/// 1) 初始化该结构的时间复杂度不能超过O(N*logN)
/// 2) 三个查询的时间复杂度不能超过O(logN)
/// 3) 查询时，认为arr的下标从1开始
///
/// 示例：
/// arr = [ 1, 1, 2, 3 ];
/// QuerySum(1, 3) -> 4
/// QueryAim(2, 4) -> 50
/// QueryMax(1, 4) -> 3
///
/// 算法思路：
/// - QuerySum: 使用前缀和数组，O(1)时间复杂度
/// - QueryMax: 使用线段树，O(logN)时间复杂度
/// - QueryAim: 使用前缀和+平方和数组，结合数学公式推导，O(1)时间复杂度
///   公式：sum((s-ai)^2) = (n-1)*s^2 + sum(ai^2)，其中n = r-l+1
/// </remarks>
public class Query3Problems
{
    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== Query3Problems 测试 ===");

        // 测试用例1：基本功能测试
        int[] arr1 = [1, 1, 2, 3];
        var q1 = new Query(arr1);
        Console.WriteLine($"测试1 - QuerySum(1, 3): 期望=4, 实际={q1.QuerySum(1, 3)}");
        Console.WriteLine($"测试1 - QueryAim(2, 4): 期望=50, 实际={q1.QueryAim(2, 4)}");
        Console.WriteLine($"测试1 - QueryMax(1, 4): 期望=3, 实际={q1.QueryMax(1, 4)}");

        // 测试用例2：单个元素
        int[] arr2 = [5];
        var q2 = new Query(arr2);
        Console.WriteLine($"测试2 - QuerySum(1, 1): 期望=5, 实际={q2.QuerySum(1, 1)}");
        Console.WriteLine($"测试2 - QueryAim(1, 1): 期望=0, 实际={q2.QueryAim(1, 1)}");
        Console.WriteLine($"测试2 - QueryMax(1, 1): 期望=5, 实际={q2.QueryMax(1, 1)}");

        // 测试用例3：相同元素
        int[] arr3 = [2, 2, 2, 2];
        var q3 = new Query(arr3);
        Console.WriteLine($"测试3 - QuerySum(2, 3): 期望=4, 实际={q3.QuerySum(2, 3)}");
        Console.WriteLine($"测试3 - QueryAim(1, 4): 期望=144, 实际={q3.QueryAim(1, 4)}"); // 修正：[2,2,2,2], s=8, 目标值=4*(8-2)^2=144
        Console.WriteLine($"测试3 - QueryMax(1, 4): 期望=2, 实际={q3.QueryMax(1, 4)}");

        // 测试用例4：包含负数
        int[] arr4 = [-1, 2, -3, 4];
        var q4 = new Query(arr4);
        Console.WriteLine($"测试4 - QuerySum(1, 4): 期望=2, 实际={q4.QuerySum(1, 4)}");
        Console.WriteLine($"测试4 - QueryAim(2, 3): 期望=13, 实际={q4.QueryAim(2, 3)}"); // 修正：[2,-3], s=-1, 目标值=(-1-2)^2+(-1+3)^2=9+4=13
        Console.WriteLine($"测试4 - QueryMax(1, 4): 期望=4, 实际={q4.QueryMax(1, 4)}");

        // 测试用例5：大数测试
        int[] arr5 = [10, 20, 30, 40, 50];
        var q5 = new Query(arr5);
        Console.WriteLine($"测试5 - QuerySum(2, 4): 期望=90, 实际={q5.QuerySum(2, 4)}");
        Console.WriteLine($"测试5 - QueryAim(1, 3): 期望=5000, 实际={q5.QueryAim(1, 3)}"); // 修正：[10,20,30], s=60, 目标值=(60-10)^2+(60-20)^2+(60-30)^2=2500+1600+900=5000
        Console.WriteLine($"测试5 - QueryMax(1, 5): 期望=50, 实际={q5.QueryMax(1, 5)}");

        // 测试用例6：复杂情况
        int[] arr6 = [1, -1, 2, -2, 3, -3];
        var q6 = new Query(arr6);
        Console.WriteLine($"测试6 - QuerySum(1, 6): 期望=0, 实际={q6.QuerySum(1, 6)}");
        Console.WriteLine($"测试6 - QueryAim(1, 6): 期望=28, 实际={q6.QueryAim(1, 6)}"); // 修正：[1,-1,2,-2,3,-3], s=0, 目标值=1+1+4+4+9+9=28
        Console.WriteLine($"测试6 - QueryMax(3, 4): 期望=2, 实际={q6.QueryMax(3, 4)}");

        Console.WriteLine("=== 测试完成 ===");
    }

    /// <summary>
    /// 线段树，支持区间更新和区间最大值查询
    /// </summary>
    public class SegmentTree
    {
        /// <summary>
        /// 延迟更新标记数组
        /// </summary>
        private readonly int[] _change;

        /// <summary>
        /// 区间最大值数组
        /// </summary>
        private readonly int[] _max;

        /// <summary>
        /// 更新标记数组，记录是否需要向下传递更新
        /// </summary>
        private readonly bool[] _updateArray;

        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="n">数组大小</param>
        public SegmentTree(int n)
        {
            _max = new int[n << 2];
            _change = new int[n << 2];
            _updateArray = new bool[n << 2];
            for (var i = 0; i < _max.Length; i++) _max[i] = int.MinValue;
        }

        /// <summary>
        /// 向上更新，用子节点的信息更新父节点
        /// </summary>
        /// <param name="rt">当前节点索引</param>
        private void PushUp(int rt)
        {
            _max[rt] = Math.Max(_max[rt << 1], _max[(rt << 1) | 1]);
        }

        /// <summary>
        /// 向下传递延迟更新标记
        /// </summary>
        /// <param name="rt">当前节点索引</param>
        /// <param name="ln">左子树元素个数</param>
        /// <param name="rn">右子树元素个数</param>
        private void PushDown(int rt, int ln, int rn)
        {
            if (_updateArray[rt])
            {
                _updateArray[rt << 1] = true;
                _updateArray[(rt << 1) | 1] = true;
                _change[rt << 1] = _change[rt];
                _change[(rt << 1) | 1] = _change[rt];
                _max[rt << 1] = _change[rt];
                _max[(rt << 1) | 1] = _change[rt];
                _updateArray[rt] = false;
            }
        }

        /// <summary>
        /// 区间更新操作
        /// </summary>
        /// <param name="left">更新区间左边界</param>
        /// <param name="right">更新区间右边界</param>
        /// <param name="c">更新值</param>
        /// <param name="l">当前节点区间左边界</param>
        /// <param name="r">当前节点区间右边界</param>
        /// <param name="rt">当前节点索引</param>
        public void Update(int left, int right, int c, int l, int r, int rt)
        {
            if (left <= l && r <= right)
            {
                _updateArray[rt] = true;
                _change[rt] = c;
                _max[rt] = c;
                return;
            }

            var mid = (l + r) >> 1;
            PushDown(rt, mid - l + 1, r - mid);
            if (left <= mid) Update(left, right, c, l, mid, rt << 1);
            if (right > mid) Update(left, right, c, mid + 1, r, (rt << 1) | 1);
            PushUp(rt);
        }

        /// <summary>
        /// 区间查询最大值
        /// </summary>
        /// <param name="L">查询区间左边界</param>
        /// <param name="R">查询区间右边界</param>
        /// <param name="l">当前节点区间左边界</param>
        /// <param name="r">当前节点区间右边界</param>
        /// <param name="rt">当前节点索引</param>
        /// <returns>区间最大值</returns>
        public int Query(int L, int R, int l, int r, int rt)
        {
            if (L <= l && r <= R) return _max[rt];
            var mid = (l + r) >> 1;
            PushDown(rt, mid - l + 1, r - mid);
            var left = 0;
            var right = 0;
            if (L <= mid) left = Query(L, R, l, mid, rt << 1);
            if (R > mid) right = Query(L, R, mid + 1, r, (rt << 1) | 1);
            return Math.Max(left, right);
        }
    }

    /// <summary>
    /// 查询结构，支持三种高效的区间查询操作
    /// </summary>
    public class Query
    {
        /// <summary>
        /// 数组长度+1（因为下标从1开始）
        /// </summary>
        private readonly int _m;

        /// <summary>
        /// 线段树，用于最大值查询
        /// </summary>
        private readonly SegmentTree _st;

        /// <summary>
        /// 前缀和数组，sum1[i]表示arr[1..i]的累加和
        /// </summary>
        private readonly int[] _sum1;

        /// <summary>
        /// 平方和前缀数组，sum2[i]表示arr[1..i]的平方累加和
        /// </summary>
        private readonly int[] _sum2;

        /// <summary>
        /// 构造函数，初始化查询结构
        /// </summary>
        /// <param name="arr">输入数组</param>
        public Query(int[] arr)
        {
            var n = arr.Length;
            _m = arr.Length + 1;
            _sum1 = new int[_m];
            _sum2 = new int[_m];
            _st = new SegmentTree(_m);

            // 构建前缀和数组和线段树
            // 时间复杂度：O(N*logN)
            for (var i = 0; i < n; i++)
            {
                _sum1[i + 1] = _sum1[i] + arr[i];
                _sum2[i + 1] = _sum2[i] + arr[i] * arr[i];
                _st.Update(i + 1, i + 1, arr[i], 1, _m, 1);
            }
        }

        /// <summary>
        /// 查询区间累加和
        /// </summary>
        /// <param name="l">区间左边界（下标从1开始）</param>
        /// <param name="r">区间右边界（下标从1开始）</param>
        /// <returns>区间累加和</returns>
        /// <remarks>
        /// 时间复杂度：O(1)
        /// 使用前缀和数组：sum[l..r] = sum1[r] - sum1[l-1]
        /// </remarks>
        public int QuerySum(int l, int r)
        {
            return _sum1[r] - _sum1[l - 1];
        }

        /// <summary>
        /// 查询区间目标值
        /// </summary>
        /// <param name="l">区间左边界（下标从1开始）</param>
        /// <param name="r">区间右边界（下标从1开始）</param>
        /// <returns>区间目标值</returns>
        /// <remarks>
        /// 时间复杂度：O(1)
        /// 数学公式：sum((s-ai)^2) = (n-2)*s^2 + sum(ai^2)，其中s是区间和，n是区间长度
        /// 公式推导：sum((s-ai)^2) = n*s^2 - 2s*sum(ai) + sum(ai^2) = n*s^2 - 2s*s + sum(ai^2) = (n-2)*s^2 + sum(ai^2)
        /// </remarks>
        public int QueryAim(int l, int r)
        {
            var sum = QuerySum(l, r);
            var sumPower2 = sum * sum;
            var n = r - l + 1;
            // 正确公式推导：sum((s-ai)^2) = (n-2)*s^2 + sum(ai^2)，其中s是区间和，n是区间长度
            // 展开过程：sum((s-ai)^2) = n*s^2 - 2s*sum(ai) + sum(ai^2) = n*s^2 - 2s*s + sum(ai^2) = (n-2)*s^2 + sum(ai^2)
            return _sum2[r] - _sum2[l - 1] + (n - 2) * sumPower2;
        }

        /// <summary>
        /// 查询区间最大值
        /// </summary>
        /// <param name="l">区间左边界（下标从1开始）</param>
        /// <param name="r">区间右边界（下标从1开始）</param>
        /// <returns>区间最大值</returns>
        /// <remarks>
        /// 时间复杂度：O(logN)
        /// 使用线段树实现区间最大值查询
        /// </remarks>
        public int QueryMax(int l, int r)
        {
            return _st.Query(l, r, 1, _m, 1);
        }
    }
}